package Search;

/**
 * 二分搜索
 * leetcode 704
 */
public class binarySearch {
    public static void main(String[] args){
        System.out.println("binary Search!");
        binarySearch binarysearch=new binarySearch();
        int[] nums = {-1,0,3,5,9,12};
        System.out.println(binarysearch.search(nums, 9));
    }
    public int search(int[] nums, int target){
        // 递归
        //return search(nums, target,0, nums.length-1);

        //循环
        return search(nums, target, 1);
    }
    public int search(int[] nums, int target, int flag){
        int left=0, right=nums.length-1, mid=0;
        while(left<=right){
            mid = (left+right)/2;
            if (nums[mid]==target){
                return mid;
            }
            else if(nums[mid]>target){
                right = mid-1;
            }else if(nums[mid]<target){
                left = mid+1;
            }
        }
        return -1;
    }


    /**
     * 递归 二分法
     * @param nums
     * @param target
     * @param l
     * @param h
     * @return
     */
    public int search(int[] nums, int target, int l ,int h){
        if (l>h){
            return -1;
        }
        int mid = (h+l)/2;
        System.out.println(mid);
        //判断选取元素与已知是否相等
        if (nums[mid] == target){
            return mid;
        }

        // 选取右边部分
        else if (nums[mid]<target){
            return search(nums, target, mid+1, h);
        }

        //选取左边部分
        else if (nums[mid]>target){
            return search(nums, target, l, mid-1);
        }
        return -1;
    }

}
